When routing is applied in a wireless network, such a network is often denoted a multihop network. In a multihop network, nodes out of reach from each other can benefit from intermediate located nodes that can forward their messages from the source towards the destination. Traditionally, multihop networks have been associated with so called ad hoc networks where nodes are mostly mobile and no central coordinating infrastructure exists. However, the idea of multihop networking can also be applied when nodes are fixed. One such scenario targets rural area Internet access and uses fixed nodes attached to the top of house roofs, lamp posts and so forth.
Although some research has been ongoing in the area of multihop since the early 1970's, relatively few of those research efforts have been directed towards QoS provisioning for multihop networks. The reason being that QoS support in multihop networks is considered to be of immense complexity. Unpredictable mobility, seemingly randomly changing traffic patterns, unreliable wireless channels, computational complexity as well as other detrimental effects are the cause of this view. Yet some researchers have tried to tackle the QoS challenge for multihop networks. The most interesting and promising research in this area have focused on using some sort of slotted TDMA (Time Division Multiple Access) like MAC (Medium Access Control) structure as a basis.
The state-of-the-art with respect to multihop networks providing collision free channels, enabling QoS routes to be established between a source node and a destination node, will now be described below. These kinds of protocols are often referred to as QoS routing protocols. As opposed to general routing protocols, QoS routing requires not only to find a route from a source to a destination, but the route must also satisfy the end-to-end QoS requirements, often given in terms of bandwidth and/or delay, e.g. to support real-time multimedia communication. The state-of-the-art QoS routing protocols might be divided into two different groups, henceforth referred to as separated channel access and routing schemes and integrated channel access and routing schemes. In the former group, the task of routing and channel allocation is separated into two different algorithms, i.e. first a route is found and thereafter the channel allocation is performed, whereas the second group takes a more or less integrated approach to channel allocation and routing.
For a better understanding of the QoS routing schemes of the prior art, it may be useful to begin with a brief overview of the OSI (Open Systems Interconnect) model for networking. The OSI model includes seven different protocol layers: the physical layer (1), the link layer (2), the network layer (3), the transport layer (4), the session layer (5), the presentation layer (6) and the application layer (7). The physical layer, which relates to the physical aspects of networking such as transmission media, transmission devices and data signals, is sometimes not seen as a protocol layer. For simplicity however, all layers will be referred to as protocol layers. Among other things, the link layer establishes and maintains links between communication devices and controls access to the network medium. The main responsibilities of network layer include switching, routing and gateway services. The transport layer is responsible for delivering frames between services on different devices. The session layer manages dialog control and session administration. The presentation layer is responsible for the presentation of data, and the application layer is concerned with the provision of services on the network and provides an interface for applications to access the network.
Separated Channel Access and Routing Schemes
The separated QoS routing protocols use generic QoS measures and are not tuned to a particular MAC layer, i.e. layer 2. In order to be able to guarantee that the QoS requirements are fulfilled, these protocols have to be enhanced with a MAC protocol providing collision free access to the channel.
Insignia
INSIGNIA [1] is an end-to-end IP based in-band-signaling framework for providing QoS in ad-hoc networks. In-band signaling means that every packet carry all information needed to establish a reservation. The QoS mechanism is independent of both the ad-hoc routing protocol used (reference is made to for example [2] or [3]) and the link layer technology, although the final received QoS will heavily depend upon these features. The operation of the framework may be described as follows: A route from the source to the destination is found by the ad-hoc routing protocol on layer 3. Since every packet carry the necessary information to reserve the necessary bandwidth, data packets may start to traverse the route as soon as it has been established which leads to fast reservation. When a node on the route from the source to the destination receives a packet from a flow for which it has not reserved capacity (indicated by one bit in the header), it reserves the requested capacity if possible.
Ticket Based Probing
As was the case for INSIGNIA, Ticket Based Probing (TBP) [4] is a pure layer 3 protocol in that all signaling is performed on this layer and that it needs the support of layer 2 (MAC) to decide whether a reservation may be accepted or should be rejected. TBP however is a true ad-hoc routing protocol. The main aim in reference [4] is to localize the search for feasible paths between source and destination to just a portion of the network instead of flooding the whole network as is usual in ad-hoc routing protocols. More specifically, they want to search only a small number of paths from source to destination, instead of making an expensive exhaustive search. This is achieved by issuing tickets. A ticket is the permission to search one path and hence, the maximum number of paths searched is bounded by the number of tickets. When an intermediate node on the path from source to destination receives a ticket it has to decide to which node(s) the ticket should be forwarded. To do this, the node uses state information to guide the limited packets along the best routes. A distance vector protocol is used to gather this state information which consists of end-to-end delay, bandwidth and cost.
Examples of Conflict Free Scheduling Algorithms
In [6], Nelson and Kleinrock introduced the concept of Spatial TDMA (STDMA), where timeslots (TS) are spatially reused. This work may be regarded as the father of all other scheduling algorithms aiming at providing conflict free schedules. The idea is to determine sets of non-interfering (or non-colliding) links. This assumes a stationary network, and the sets need to be recalculated if the network changes sufficiently. Those sets are preferably selected such that it allows each node in the network to transmit at least once. Each timeslot in a TDMA frame is then assigned a set of links (transmission sets) that can transmit without interfering each other. The same schedule is subsequently repeated each STDMA frame.
The scheme(s) presented in [8] and [9] could be viewed as a direct offspring of STDMA. In previous works on STDMA, the connectivity of the network graph is used to decide if interference occurs. Such an approach does not capture the total interference in the network. Instead, in the scheme(s) of [8] and [9], the generation of STDMA schedules is based on the SIR value for each link.
STDMA and its offspring are pretty much designed for off-line or centralized calculation of the transmission sets. In ad hoc networks, this is not a sensible approach. A particular layer 2 scheme, which ensures distributed and collision free operation, called Collision-Free Topology-Dependent Channel Access Scheduling or CTMA in short is presented in [7].
“Integrated” Channel Access and Routing Schemes
The “integrated” QoS routing algorithms are based on the assumption that the ad hoc network may be modeled as a graph, and all of them are on-demand protocols, i.e. the route search is only done after a route have been requested from a higher layer protocol. Furthermore, conventional integrated QoS routing algorithms generally assume TDMA, fixed transmit power and omni-directional antennas. In a graph, two nodes are called neighbors if they are able to communicate with one another and this is represented by connecting the two nodes with a link in the graph model. Two nodes are connected if the distance between them does not exceed some predetermined value; i.e. packets are received without error in absence of external interference from other nodes. It is also assumed that only neighbors are interfering with one another. In a multihop packet radio network modeled with graphs, transmissions are often modeled to interfere in two ways, henceforth referred to as primary interference and secondary interference. Primary interference occurs when the node is supposed to do more than one thing in a single timeslot, for instance transmit and receive in the same timeslot. Secondary interference occurs when a receiver R tuned to a particular transmitter T is within range of another transmitter whose transmission, though not intended for R, interfere with the transmission of T at R. When using a graph model, it is sufficient to prevent all neighbors of R transmitting in the same timeslot as T to avoid secondary interference. When describing the various integrated QoS routing protocols below, they have been classified according to what level of interference they are considering—interference free channel, only primary interference considered and both primary and secondary interference considered, since this highly affects the way the protocol is designed.
Most existing ad hoc routing protocols are only concerned with the existence of a shortest path route between two nodes in the ad hoc network without guaranteeing its quality. As previously described, the aim for ad hoc QoS routing protocols is to set up a path/channel from a source node to a destination node fulfilling some requirements regarding bandwidth and/or delay to be able to support real-time multimedia communication. To do this, conventional integrated QoS routing protocols normally consider the bandwidth on a link when searching for a route from source to destination. The bandwidth requirement is then realized by reserving time slots on the links on the path. The main advantage of this approach, when compared to ordinary ad-hoc routing protocols, is that the QoS requirements can be fulfilled. Compared to completely separated QoS routing protocols, this means that QoS provisioning can be achieved with a better network utilization.
To calculate the available bandwidth in this environment, it is incorrect to simply compute the minimum bandwidth of the links along the path as is done in wireline networks. The cause of this is that the available bandwidth is shared among the neighboring nodes. A simple example of this is the following where only primary interference is considered: Suppose node A wants to communicate with node C via node B. The available free slots for A to communicate with B is 1, 2, 3 and 4 and the same holds for the link from B to C. If this would have been a wireline (or an interference free channel) network the available capacity would have been 4 slots, whereas in this case the capacity is 2 slots. The reason for this is that the intersection of common free slots on links A to B and B to C is not an empty set and a node is not able to both transmit and receive in the same slot. Further, assume that the available free slots to communicate from A to B and B to C are 1, 2, 3 and 4 as well as 3 and 4 respectively. If slots 1 and 2 are reserved for communication from A to B and slots 3 and 4 for communication from B to C, the available bandwidth from A to C is 2. On the other hand if slots 3 and 4 are reserved for communication from A to B it will mean that no communication may take place from B to C and the available bandwidth from A to C would have been 0 in this case. Protocols that are able to pinpoint this problem and solve it will be said to be able to perform optimal scheduling henceforth. There are two problems involved in this path bandwidth computation process. The first problem is how station B (here it is assumed that B is responsible for reserving capacity on the link from A to B) knows the set of common free slots of two adjacent links, and the second problem is how to share this information with its neighbors. To solve these problems, the stations have to exchange some messages with each other.
Interference Free Channel
Reference [16] describes a multi-path QoS routing protocol that is based on the ticket based approach presented in [4]. The expression “multi-path” refers to the case where the reserved capacity from source to destination may be split into several subpaths, each serving part of the original requested capacity. However, this work is assuming quite an ideal model in that the bandwidth of a link may be determined independently of its neighboring links. To support this assumption, it is assumed that each host has multiple transceivers that may work independently of one another and that each link is assigned a code that is distinct from those codes used by its two-hop neighbors to avoid collision. A two hop neighbor is a neighbor of a neighbor—in the example above A and C are two hop neighbors.
Only Primary Interference Considered
A less stringent assumption than interference free channel is made in [12], [13] and [15], where a CDMA-over-TDMA channel model is assumed, implying that the use of a time slot on a link is only dependent of the status of its neighboring links (i.e. they only consider primary interference). The focus in these three references is the calculation of the available bandwidth on the path from source to destination but the way the required information is gathered differs.
The general operation of [12] and [13] will now be described briefly. On receiving an RREQ (Resource REQuest) the bandwidth is calculated from the source to this node. The bandwidth may be computed in an optimal way since information is exchanged with its neighbors about the available free slots prior to the calculation of the available bandwidth and that the RREQ message includes the slots used for the previous link on the path from the node to the source. The RREQ is dropped if the result does not satisfy the QoS requirement. As is to be expected the destination will receive more than one RREQ each indicating a unique feasible path from source to destination. The destination will choose one of the paths and issue an RREP (Route REPly) message. As the RREP message traverses back to the source, each node along the path reserves those free slots which were calculated in advance.
In [5], a protocol for QoS routing in an IEEE 802.11 network is presented that utilize the bandwidth calculation algorithms described above.
In [15], instead of calculating the available bandwidth hop-by-hop, each RREQ packet records all link state information from source to destination. In this way the destination is able to calculate the best path from source to destination and issues a RREP message along the chosen path. An option for multipath routing is also presented in the reference and is easily achieved since the destination has all information of all available paths from source to destination. The algorithm proposed in [15] targets a flow network; i.e. supports multiple different flows. It is the task of the destination node to determine the flow network from the source that fulfils the bandwidth requirement. Although such a solution has the potential to provide a close to optimal route, interference being neglected, it also put immense computational burden on the destination node.
Both Primary and Secondary Interference Considered
Cluster Based
In the cluster-based networks described in [10], [11], [14] and [18], a node could be a cluster head, a gateway or just a usual node. Once a node is chosen as a cluster head, all its neighbors belong to the same cluster. A node that belongs to two or more clusters plays the role of a gateway. CDMA is used to partition the clusters by assigning different code sequences to different clusters, and TDMA is enforced within a cluster. By doing so they claim that secondary interference only have to be considered within the cluster, since it is assumed that the interference in between clusters is negligible. To spread the information of available slots within the cluster every node periodically transmits a “free-slot” message that contains its slot reservation status. Since the cluster head can hear all other nodes in the cluster, it has complete knowledge of the reservation status in the cluster. Since the cluster head, as all nodes in the cluster, is obliged to transmit the “free slot” message all nodes will eventually know the slot reservation within the whole cluster. This makes the computation of available bandwidth simple. The available bandwidth computation and signaling is then carried out independently at each node on a hop-by-hop basis.
The scheme proposed in [18] is not really an integrated approach. Instead, a hierarchical scheme is proposed—first capacity allocation is made both at the node (link) level and at the flow level (in both these steps fixed routing is assumed), then a distributed version of the Bellman-Ford algorithm is used for the final route selection. It is assumed that every node's allocated slots get assigned to the appropriate portion of the time frame by some mechanism, but the MAC layer is not considered. Further, it is required that one central entity gathers all the information, performs the calculations and then distributes the final result, i.e. it is a centralized approach.
In the references [17] and [19] mentioned below, an ordinary TDMA/slotted structure is assumed and hence the protocols will have to consider both primary and secondary interference with regards to all nodes in the network.
Liao
The scheme presented in [17] requires that a node first of all have to know the partial graph of its own locality (this means that a node has to know how its neighbors and neighbor's neighbors (usually referred to as 2-hop-neighbors) are interconnected). Further, a node also has to have complete knowledge of the slots that the neighbors are receiving and transmitting in (note, it is not enough to know if the node is busy or not). This also holds for its 2-hop-neighbours. In order to create these data structures, a host needs to periodically broadcast this information to its neighbors and these have to rebroadcast this to their neighbors. With this information it is possible to perform the routing and slot allocation. The rule is (as in most other papers) that a slot may only be allocated if the two nodes commonly indicate a slot as free and that the sending node does not interfere with any of its neighbors. Note this scheme is not able to compute the optimal path bandwidth.
Zhu
The scheme presented in [19] resembles some of the approaches that only consider primary interference, but is not able to calculate the available bandwidth optimally. Nothing is said about how a node knows which slots it is permitted to send in with respect to secondary interference with other nodes not on the path from source to destination. It is merely stated that it is the job of the underlying slot assignment protocol at the MAC layer to determine bow the nodes negotiate with each other to ensure that slots are assigned to the corresponding transmitters and are respected by their neighbors.
Additional State-of-the-art Solutions
In [20], a graph model is built up by assuming that two nodes are connected if the distance between them does not exceed some predetermined value, i.e. packets are received without error in absence of external interference from other nodes. A relatively realistic model on secondary interference is used. Two or more stations may transmit in the same time slot provided that the Signal-to-Interference Ratio (SIR) in all receiving nodes is above a certain threshold. The routing decision is based on minimum hop connections between source-destination pairs. Given a network topology (depicted by the graph model) the number of hops and possible paths may be found by broadcasting a packet through the network and counting the number of nodes visited. When multiple paths with equal number of hops between source and destination is found previous slot assignments and relative traffic load are used as decision criteria, so as to accomplish load balancing in the network. By doing so congestion is less likely and the throughput may be increased. In short, the algorithm that follows five steps may be described as follows. In the first step, the graph model is used to derive the network topology. Next, a routing decision is used to produce balanced traffic between links taking into account the available capacity. Since capacity for each link is required for this routing decision, equal link capacity is considered at this step. In the third step, any conflict free scheduling algorithm, such as for example [8], may be used to generate the schedule. After this, the routing decision is taken again (fourth step), but this time based on the actual capacity given by the schedule. In the final step, the routing decision (step two or four) that produced maximum throughput for the whole network is chosen. Reference [20] is actually based on sequential and thus separated routing and scheduling/reservation. It should also be pointed out that this scheme requires a centralized path and resource assignment determination.
References [21-22] are not related to the issue of routing on the network layer, but rather concern adaptive wireless communication, with parameters on the physical layer and the MAC layer being adaptively modified by a base station controller.
Problems Associated with the State-of-the-art Solutions
The separated channel access and routing schemes are generally far from optimal. The reason is simply that the problem of assigning routes and channel resources has been subdivided into two simpler problems. In addition, the separated schemes often assume off-line and centralized determination of path and resource assignments. This means that they are relatively poor at handling mobility, as information must be collected, processed and subsequent results disseminated to involved nodes.
Although several good ideas for some form of “integrated” channel access and routing have been presented, important radio aspects are entirely neglected. Therefore, the usefulness of the algorithms can be questioned. For instance, an overly simplistic assumption that nodes uses orthogonal codes so no transmitting node interfere with any other receiving node is used in several of the papers. It is not just incorrect, as in practice codes are not perfectly orthogonal due to e.g. delay spread and hence will cause detrimental interference, but it is also an inefficient use of valuable resources. The orthogonality of signals is a result of a bandwidth (BW) expansion, and the bandwidth could probably be used better through sending data at higher rates. The path and resource assignment procedure proposed in conventional “integrated” channel access and routing schemes is also very much simplified and may sometimes advice routes that are not feasible in practice.